/*************************************************************************
	> File Name: test.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 三  9/22 19:41:25 2021
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include "uthash.h"
#include <stdbool.h>

#define HASH_FIND_LONG(head, findint, out) HASH_FIND(hh, head, findint, sizeof(long), out)
#define HASH_ADD_LONG(head, intfield, add) HASH_ADD(hh, head, intfield, sizeof(long), add)

struct HashTable {
    long key;
    UT_hash_handle hh;
};

void insert(struct HashTable** hashTable, long ikey) {
    struct HashTable* tmp;
    HASH_FIND_LONG(*hashTable, &ikey, tmp);
    if (tmp == NULL) {
        tmp = malloc(sizeof(struct HashTable));
        tmp->key = ikey;
        HASH_ADD_LONG(*hashTable, key, tmp);
    }
}

bool count(struct HashTable** hashTable, long ikey) {
    struct HashTable* tmp;
    HASH_FIND_LONG(*hashTable, &ikey, tmp);
    return tmp == NULL;
}

//实现最小堆
typedef struct {
    long *data;
    int cnt;
    int capacity;
} priority_queue;

priority_queue *init(int n) {
    priority_queue *q = (priority_queue *)malloc(sizeof(priority_queue));
    q->data = malloc(sizeof(long) * (n + 1));
    q->cnt = 0;
    q->capacity = n;
    return q;
}

int empty(priority_queue *q) {
    return q->cnt == 0;
}

long top(priority_queue *q) {
    return q->data[1];
}

int push(priority_queue *q, long val) {
    if (q == NULL || q->cnt == q->capacity) return -1;
    int ind = ++q->cnt;
    while (ind >> 1) {
        if (val < q->data[ind >> 1]) {
            q->data[q->cnt] = q->data[ind >> 1];
            ind = ind >> 1;
        } else {
            break;
        }
    }
    q->data[ind] = val;
    return 0;
}

void pop(priority_queue *q) {
    if (q == NULL || empty(q)) return;
    //下滤 
    q->data[1] = q->data[(q->cnt)--]; //堆尾元素放到堆顶
    long tmp = q->data[1];
    int ind = 1, child;
    while ((ind << 1) <= q->cnt) {
        child = ind << 1;
        if (child != q->cnt && q->data[child + 1] < q->data[child]) { //找到子节点中更小的那个
            child++;
        }
        if (tmp > q->data[child]) {
            q->data[ind] = q->data[child];
            ind = child;
        } else {
            break;
        }
    }
    q->data[ind] = tmp;
    //end
}

void print(priority_queue *q) {
    printf("[");
    for (int i = 1; i <= q->cnt; i++) {
        i == 1 || printf(" ");
        printf("%ld", q->data[i]);
    }
    printf("]\n");
}


int nthUglyNumber(int n){
    int factors[3] = {2, 3, 5};
    struct HashTable *hashTable = NULL;
    insert(&hashTable, 1);
    priority_queue *q = init(n * 3);
    push(q, 1);
    int ugly = 0;
    for (int i = 0; i < n; i++) {
        long curr = top(q);
        pop(q);
        ugly = (int)curr;
        for (int j = 0; j < 3; j++) {
            long next = curr * factors[j];
            if (count(&hashTable, next)) {
                insert(&hashTable, next);
                push(q, next);
                //printf("i = %d ", i);
                //print(q);
            }
        }
    }
    return ugly;
}

int main() {
    printf("%d\n", nthUglyNumber(90));
    return 0;
}
